In a Content-Addressable Memory (CAM), as distinguished from a conventional non-content-addressable memory, a data word is accessed by specifying a data value which is compared to at least part of the content of the word. For example, if a CAM system stores a personnel database and each word of CAM describes the attributes of a person such as name, age, height, and weight, all persons having a certain age could be found by comparing the desired age to the portion of each word which contains age data. In most CAM systems, all comparisons are done concurrently, or "in parallel". Parallel comparisons of a CAM system offer a major advantage over non-content-addressable memory because, in the latter case, all memory locations would need to be interrogated in a sequential fashion, thus requiring much more time to search the data.
The results of all the parallel comparisons are stored into a special memory which has gone by many names: flag bit, tag bit, match trigger, and response store. Thus, since each word has a comparison result, there is a flag bit associated with each word. Continuing with the above personnel database example, all words which contain an age parameter equal to the desired age will have their flag bit equal to `1` while those which are not equal will have their flag bit equal to `0`. Most CAM systems provide a scheme by which all words with a flag bit equal to `1` are read out of the memory. This usually requires a sequence of steps: finding a word with its flag bit equal to `1`; reading the data word out of the memory; outputting the data to another device for further processing; and turning off the flag bit so that subsequent reads will output different data words. This sequence may take more than one clock cycle, but, in the CAM system presented in this patent, all steps for a read operation occur in one clock cycle.
CAM systems commonly allow a sequence of comparison operations to be performed in order to provide greater flexibility in searching the stored data. Once again returning to the personnel database example, after the comparison operation on the age attribute has appropriately set of all flag bits, another comparison is performed on the height attribute. However, only words which have their flag equal to `1` before this comparison will have a possibility of having their flag set to `1` after this comparison. Thus, after these two comparisons have been performed, only words containing both the desired age and desired weight have their flag equal to `1`. A subsequent comparison could test for a desired height, and this process could continue for as many comparisons as desired. At each step, the new flag value is a function of both the old flag value and the comparison result. This process requires the ability to set all flags equal to `1` before the process starts.
In order to determine which bits in a word affect the outcome of a comparison, a mask register is usually provided. There is one mask register for the entire system and it has the same number of bits as a word of CAM. If, for example, a particular bit in the mask register has a value of `1`, then the one-bit comparison performed on the corresponding bit in all words of CAM will affect the comparison results. Conversely, if the mask bit is `0`, the one-bit comparison on corresponding bits will not affect the overall comparison results. In the personnel database example, a comparison on only the age parameter requires bits in the mask register corresponding to the age parameter bits to be set to `1`, while all other bits in the mask register are set to `0`. Each parameter is stored in a portion of a word referred to as a "subfield".
Some CAM systems, such as U.S. Pat. No. 3,607,702 by Gardner, et. al., allow more than one flag bit.
This allows the CAM to execute a wider variety of algorithms. Caxton Foster, in his book, Content Addressable Parallel Processors, published by Van Nostrand Reinhold Company in 1976, describes several algorithms for content-addressable systems which require more than one flag bit per word.
Returning to the example of the personnel data base, if a search to discover all persons with weight greater than 145 pounds is required, a bit-sequential algorithm is usually employed. That is, the mask register is set so only one bit in the weight parameter affects the outcome of each word's comparison. Bits in the weight parameter are scanned from most significant to least significant and each step determines some words are greater-than and some words are less-than. The process is continued until all bit positions in the weight parameter have been tested. This type of algorithm is described in detail on page 61 of Caxton Foster's book and requires at least two flag bits per word. It is seen that the execution time of this algorithm is proportional to the number of bits to be scanned. This is a huge advantage over conventional memory because it would be necessary to scan each word and compare its weight parameter to 145. To reiterate, the above described CAM system performs this algorithm in time proportional to the number of bits to be scanned, while conventional memory systems require time proportional to the number of words to be scanned. There is, however, room for improvement. If each CAM word includes the appropriate hardware, a full greater-than comparison on the entire weight parameter can be performed in one clock cycle. This, of course, requires more complicated hardware since most CAM systems only allow testing for equality or inequality. The invention presented in this patent includes such hardware in each word of CAM.
With the inclusion of less-than and greater-than comparison capability, the personnel data base could be searched for persons with weight greater than 145 pounds in one clock cycle. A further improvement would be obtained if a one-clock-cycle search could be performed to find people with age less than 22 years, height greater than 74 inches, and weight greater than 145. This further complicates the hardware since all three comparisons must take place in parallel. This requires all three pieces of data (i.e. 22, 74, and 145) and the type of comparison to be performed on each subfield (i.e. greater-than, less-than, etc.). All people found to have these characteristics are in a subset of the entire set of people contained in the database. This subset could be saved for future use by allocating a flag to remember which people are in this particular subset. The subset could then be altered to include those words, or people, which pass the above test and pass an additional test for age greater than 18 years and height less than 76 inches. This new subset could overwrite the old subset by using the same flag bit, or it could use another flag bit and preserve the old subset. Thus, the total number of subsets that a CAM of this type could keep track of at any one instant in time is equal to the number of flag bits in each word. The operation of multiple subfield comparisons occurring in the same clock cycle is referred to as a "query" and is unique to the present patent.
Only one other patent is known to be able to perform less-than and greater-than type comparisons in one clock cycle. This is U.S. Pat. No. 3,320,592 by Rogers, et.al. entitled "Associative Memory System". This patent specifies three flag bits called G.sub.FF, L.sub.FF, and Active Flip-Flop. The Active Flip-Flop performs the same role as the special "data invalid" flag described above. G.sub.FF and L.sub.FF store the results of greater-than-or-equal-to and less-than-or-equal-to comparisons respectively. To define a subset of words within a range of values, both of these flip-flops need to be used. The Rogers patent does not allow a provision for keeping track of multiple subsets of the data or Boolean operations between such subsets. The Rogers patent does not allow multiple subfields within a word and thus does not lend itself to processing spatially distributed data. It does not include a means of "or-ing" flag bits together and thus requires the execution of a read cycle to determine that no data words are in the searched range of values. In order to test for the equality condition, two clock cycles must be used rather than one. Finally, the Rogers patent is designed in cryogenic logic circuitry which is completely different from the FET or CMOS technology used in the present patent application.
U.S. Pat. No. 3,389,377 by Cole, et.al. entitled "Content Addressable Memories" provides a means for computing less-than and greater-than comparisons, but requires a bit sequential search technique. It also suffers from having only one true flag bit, called a "Match Store", making it impossible to process more than one subset at a time. It also does not provide for multiple subfields within words or for an "or" of the flag bits.
TRW LSI Products, Inc. of La Jolla, Calif., a subsidiary of TRW, has published a preliminary specification for a "VHSIC Window Addressable Memory (WAM)". This integrated circuit can simultaneously perform eight greater-than and eight less-than comparisons every two clock cycles. Thus, it can handle eight "windows" at a time, and each window can be divided into a maximum of twelve subfields. This TRW product differs considerably from the CAM of the present patent. In the present patent, data is stored in the integrated circuit and queries are performed sequentially. In the TRW chip, query data (called windows by TRW) are stored in the chip and data is scanned sequentially. This difference may be summed up by stating the present patent performes operations which are data parallel and query sequential, while the TRW chip is query parallel and data sequential. Clearly, these chips perform different functions. The TRW chip is appropriate for applications where the desired search space is known in advance and data flows through the chip once. Thus it can act as a filter. The present patent is appropriate for applications where the data is constant and many different queries are performed on the same data. The TRW chip does not provide anything similar to the flag bits of the present patent and therefore cannot manipulate sets of data with the efficiency of the present invention.
The CAM of the present patent is able to test for either equality, less-than, less-than-or-equal-to, greater-than, greater-than-or-equal-to, or inequality on each subfield during one clock cycle. This set of operations shall be referred to herein as a "query comparison."
If many subsets have been formed, it would be useful to perform operations such as union and intersection on groups of subsets. For example, if three subsets were defined in the personnel database, it might be desirable to know which people are members of either subset 1 or subset 2 but are not members of subset 3. These types of operations are possible in the CAM presented here because a selectable Boolean operation can be performed on sets of flag bits. This Boolean operation can take place in a separate clock cycle or in the same clock cycle with a comparison operation and use the comparison result as input to the Boolean operation in the present invention.
For a CAM with all of the above properties, a more practical application would be in the area of processing spatially distributed data points. Consider an n-dimensional space sparsely populated with data points. Each word of CAM would represent one of the data points by storing its position in the n-space. Since position in n-space requires an n-tuple (if n=3, the 3-tuple could also be called an "ordered triple"), each word of CAM is required to store n numbers. Each of these numbers is analogous to one of the parameters attributed to a person in the above personnel database example. These parameters are referred to as "subfields" of the word of CAM. When, for example, a less-than operation is performed on both parameters in 2-space, or x-y plane, all data points in the CAM are tested to see if they lie in a particular quadrant of the space. If the comparison is x&lt;100 and y&lt;50, than the point (98,48) would lie in the quadrant while the point (102,30) would not lie in the quadrant. The result of this comparison would define a subset of the entire set of points and the members of this subset would be indicated by having a particular flag bit set to `1`. If another comparison such as x&gt;90 and y&gt;45 were performed to form another subset, and the intersection of these two subsets were found, a new subset would be generated such that only the points in the rectangular region 90&lt;x&lt;100 and 45&lt;y&lt;50 would be included in the subset. Thus, it is seen that this CAM can generate and manipulate regions in an n-dimensional space. Arbitrarily shaped regions could be generated by taking unions and intersections of various other regions. This CAM processing system can "query" an n-dimensional space in order to determine which data points lie in particular regions of the space. Once a region, or subset, is defined in this way, members of the set may be read from the CAM for other types of processing. A very useful function included here is the ability to determine whether any data points at all reside in a particular region in the space.
In a typical pattern recognition system, a large number of objects may be included as recognizable entities. An example of this would be the set of all types of airplanes and rockets. In a radar system, each type of aircraft generates a certain type of response to the radar. This radar profile is a complicated signal reflected by the aircraft. It is possible to extract characteristics, or features, from this signal. So, a transform occurs from the signal domain to the feature domain. This feature domain may have a very large number of dimensions and is usually called a "feature space". Each known type of aircraft has a radar profile which maps into this feature space and thus a sparsely populated n-dimensional space is formed. When an unidentified aircraft is seen by the radar, its radar profile is mapped into the feature space to see if it matches any of the known aircraft types. Since an exact match is very unlikely, the closest match is presumed to be the best guess of the unknown aircraft type. The conventional way to find the closest match would be to compare the unknown airplanes features to the features of each known aircraft in a one-by-one, or sequential, manner. For each comparison, the Euclidean distance between the known and unknown is computed. The smallest Euclidean distance indicates the best match.
In the CAM system described here, a sequential calculation of Euclidean distances is not required. Rather, in the feature space, an n-dimensional spherical region centered at the location of the unknown is formed. This region is expanded or shrunk until only one data point representing a known aircraft is contained in the region. The one left in the region must be the closest match to the unknown. An alternate scheme would be to create a large region around the location of the unknown which at least tells which of the known aircraft types are close. These close matches are then compared one-by-one to to the unknown to determine which is actually closest. In either case, the the CAM system's search time is at least approximately independent of the number of known airplane types, while the time required for a conventional search is proportional to the number of known airplane types. The number of known airplane types may be very large especially when a different orientation of the same airplane must be allocated different positions in the feature space.
The above search scheme could be applied to many areas of pattern recognition such as voice recognition, character recognition, and artificial vision. The CAM system described here could be applied to any problem which requires searching spatially distributed data.
The CAM system described here also includes many other useful features. One such feature is the inclusion of a special flag bit which designates the validity of the data in each CAM word. Since it is possible for the number of useful words of information stored in the CAM to be less than the total capacity of the CAM system, some words will contain invalid data. Invalid data should not be included in comparison operations. Also, when new data is written into the CAM, it must be placed into a word which contains only invalid data. When data is no longer needed, this special "data invalid" flag bit is set to `1` using the normal query operations. The signal coming from this flag bit is called FlagO. Flag bits are numbered from 0 to X-1, where X is the total number of flag bits. In this document, signal names will be italicized and a "*" appended to the end of a signal name indicates the signal is active low.
Another useful function is an "or" of flag bit values as they are generated. If the "or" of these flag bits is equal to `0`, the subset represented by these flag bits is empty. This allows a region of an n-space to be interrogated for the presence of a data point without spending an additional clock cycle in an attempt to read a data point from the region.
A very useful feature presented here is the ability to use the mask register when performing a greater-than or less-than type of operation. This means that certain bits in a subfield are treated as if they were not present in the subfield. For example, if a subfield contains the bit pattern 10110010, the mask register contains 11001111, and the subfield is tested for a less-than 10001010, the comparison is found to be true. This is because the subfield data is treated as if it is 100010 rather than 10110010 (i.e. two bits deleted because of the value of the mask register) and it is compared to 101010 rather than 10001010. This feature is useful in sectioning up a large n-space into small overlapping ones by allowing several different sets of most significant bits to be associated with one set of low order bits.
The mask register can also be used to enable or disable writing to specific bits in the CAM. This is desirable if part of the contents of a word should remain unchanged while other bits are overwritten. This feature can be used for a parallel write into bits of many words. In this mode, words of CAM that have a specific flag equal to `1` will have some of their bits overwritten. This feature is necessary to allow the CAM to perform bit serial arithmetic. To see how these algorithms work, see Foster's book, page 80.
Also included in this patent is a scheme for dividing the entire CAM system into an array of integrated circuits. This requires a mechanism to determine which word in which chip responds to a "single word" operation such as read or write. The integrated circuit, or chip, described in this patent is designed using Field-Effect Transistors (FETs). The specific technology used here for the preferred embodiment is Complimentary Metal Oxide Silicon (CMOS) integrated circuit technology.